J'ai créé ce « notebook » avec iPython Notebook, un système gratuit (et « libre ») qui peut faire des calculs symboliques, créer des graphiques, afficher des expressions mathématiques avec $\LaTeX$ et faire beaucoup d'autres choses utiles.
On commence par configurer plusieurs bibliothèques qu'on va utiliser bientôt.
In [1]:
from sympy.interactive import printing
printing.init_printing()
import sympy as sym
from sympy.mpmath import limit, inf
from sympy import Rational as frac
%pylab inline --no-import-all
On calcule la probabilité de $A_1^C$, la probabilité qu'aucun 6 apparaît dans 4 lancers d'un dé à 6 faces, est on utilise ça pour calculer $\mathbb{P}(A_1) = 1-\mathbb{P}(A_1^C)$.
In [2]:
1-frac(5,6)**4
Out[2]:
In [3]:
1-(5.0/6)**4
Out[3]:
In [4]:
1-frac(35,36)**24
Out[4]:
In [5]:
1-(35.0/36)**24
Out[5]:
On peut voir que $\mathbb{P}_1(A_1)$ est superieur à $\mathbb{P}_2(A_2)$, mais par une petite quantité.
In [6]:
def p_a(n):
denom = 6**n
num = denom - 1
return 1 - (num/denom)**(2*denom/3)
x = np.linspace(1,6)
plt.plot(x, p_a(x))
None
La limite de $\mathbb{P}_n(A_n)$ lorsque $n$ tend vers l'infini a l'air d'être un peu moins que 0.49.
$$\begin{aligned} \lim_{n \to \infty} \left[ 1 - \left(\frac{6^n-1}{6^n}\right)^{\frac{2}{3} n} \right] \end{aligned}$$
In [7]:
limit(p_a, inf)
Out[7]:
On pioche deux cartes, sans replacement. On a trois cas : Deux as, un as et une autre carte, et deux non-as.
$$\begin{aligned} \mathbb{P}(\text{deux as}) &= \frac{4}{52}\frac{3}{51}\\ \mathbb{P}(\text{as et un non-as}) &= \frac{4}{52}\frac{48}{51} + \frac{48}{52}\frac{4}{51} = 2\left(\frac{4}{52}\frac{48}{51}\right)\\ \mathbb{P}(\text{deux non-as}) &= \frac{48}{52}\frac{47}{51} \end{aligned}$$Si on pioche deux as, $\mathbb{P}(\text{blackjack} | \text{deux as}) = 0$, car $1+1=2$, $1+11=12$ et $11+11=22$. Si on pioche un as, l'autre carte doit avoir une valeur de 10, et donc $\mathbb{P}(\text{blackjack} | \text{un as et un non-as}) = \frac{4}{12} = \frac{1}{3}$. Et sans au moins un as, on ne peut pas ganger, donc on a $\mathbb{P}(\text{blackjack} | \text{deux non-as}) = 0$.
$$\begin{aligned} \mathbb{P}(\text{blackjack}) = 0 + \frac{2}{3}\left(\frac{4}{52}\frac{48}{51}\right) + 0 \end{aligned}$$
In [8]:
frac(2,3)*frac(4,52)*frac(48,51)
Out[8]:
Si le joueur a une dame de $\spadesuit$ et un 5 de $\clubsuit$, il faut qu'il reçoive une carte avec une valeur de 1, 2, 3, 4, 5, 6 ou 7 pour ne pas perdre. Il reste $4 \cdot 7 - 1 = 27$ cartes sur 50 avec la valeur necessaire, et donc il a 27 chances sur 50 de ne pas perdre.
On veut démontrer que :
$$ \mathbb{P}(\cup_{m=1}^{n} A_m) = \sum_{k=1}^n (-1)^{k+1} p_k $$ou
$$ p_k = \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}). $$Quand $n$ est égal à 1, on a
$$\begin{aligned} \mathbb{P}(A_1) &= (-1)^2 \mathbb{P}(A_1) \\ &= \mathbb{P}(A_1). \end{aligned}$$Quand $n$ est égal à 2, on a
$$\begin{aligned} \mathbb{P}(A_1 \cup A_2) &= (-1)^2 (\mathbb{P}(A_1) + \mathbb{P}(A_2)) + (-1)^3(\mathbb{P}(A_1 \cap A_2)) \\ &= \mathbb{P}(A_1) + \mathbb{P}(A_2) - \mathbb{P}(A_1 \cap A_2). \end{aligned}$$Quand on ajoute $\mathbb{P}(A_1)$ à $\mathbb{P}(A_2)$, on compte $\mathbb{P}(A_1 \cap A_2)$ deux fois, et il faut donc le soustraire.
Soit $B$ égal à $\cup_{m=1}^{n} A_m$. On peut voir que
$$\begin{aligned} \mathbb{P}(B \cup A_{n+1}) &= \mathbb{P}(B) + \mathbb{P}(A_{n+1}) - \mathbb{P}(B \cap A_{n+1}) \\ &= \mathbb{P}(B) + \mathbb{P}(A_{n+1}) - \mathbb{P}(\cup_{m=1}^{n} (A_m \cap A_{n+1})) \\ &= \left[\sum_{k=1}^n (-1)^{k+1} p_k\right] + \mathbb{P}(A_{n+1}) - \left[\sum_{k=1}^n (-1)^{k+1} q_k\right] \end{aligned}$$ou
$$\begin{aligned} p_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) & \text{et}\\ q_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k} \cap A_{n+1}). \end{aligned}$$Et maintenant, on peut voir la correspondance entre nos deux sommations :
$$\begin{aligned} \mathbb{P}(B \cup A_{n+1}) &= p_1 + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] + \mathbb{P}(A_{n+1}) - \left[\sum_{k=1}^{n-1} (-1)^{k+1} q_k\right] - (-1)^{n+1} q_n \\ &= p_1 + \mathbb{P}(A_{n+1}) + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] - \left[\sum_{k=2}^{n} (-1)^{k} q_{k-1}\right] - (-1)^{n+1} q_n \\ &= p_1 + \mathbb{P}(A_{n+1}) + \left[\sum_{k=2}^{n} (-1)^{k+1} p_{k}\right] + \left[\sum_{k=2}^{n} (-1)^{k+1} q_{k-1}\right] - (-1)^{n+1} q_n \\ &= \left[\sum_{i=1}^n \mathbb{P}(A_i)\right]- \left[\sum_{k=2}^{n} (-1)^{k+1} (p_{k} + q_{k-1})\right] - (-1)^{n+1} \mathbb{P}(A_{1} \cap \cdots \cap A_{n+1}). \end{aligned}$$Soit
$$\begin{aligned} r_k &= p_k + q_{k-1} \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) + \sum_{1 \leq i_1 \lt \cdots \lt i_{k-1} \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_{k-1}} \cap A_{n+1}) \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq {n+1}} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}). \end{aligned}$$Cela nous donne
$$\begin{aligned} \mathbb{P}(\cup_{m=1}^{n+1} A_m) &= r_1 - \left[\sum_{k=2}^n (-1)^{k+1} r_k\right] - (-1)^{n+1} r_{n+1} \\ &= (-1)^{1+1} r_1 - \left[\sum_{k=2}^n (-1)^{k+1} r_k\right] + (-1)^{(n+1)+1} r_{n+1} \\ &= \sum_{k=1}^{n+1} (-1)^{k+1} r_k, \end{aligned}$$et on peut faire l'induction.
In [9]:
from itertools import permutations
# Les lettres et les boîtes ont les indices 0, 1, 2, etc.
# Une lettre est dans boîte correcte quand les deux ont
# la même indice.
def au_moins_une_lettre_correcte(lst):
for ind, val in enumerate(lst):
if ind == val:
return True
return False
# Quand il y a N boîtes, quelle fraction des distributions sont correctes?
def compter_distributions(n):
distributions = list(permutations(range(0,n)))
correctes = [d for d in distributions if au_moins_une_lettre_correcte(d)]
return [len(correctes), len(distributions)]
map(compter_distributions, [1,2,3,4,5,6])
Out[9]:
Hélas, il n'y a pas de motif simple ici.
In [10]:
list(permutations(range(0,2)))
Out[10]:
In [11]:
list(permutations(range(0,3)))
Out[11]:
In [12]:
list(permutations(range(0,4)))
Out[12]:
Essayons les cycles de permutations:
(1)(2) (1)(23) (2)(13) (3)(12) (1)(2)(3) (1)(234) (1)(243) (2)(134) (2)(143) (3)(124) (3)(142) (4)(123) (4)(132) (1)(2)(34) (1)(3)(24) (1)(4)(23) (2)(3)(14) (2)(4)(13) (3)(4)(12) (1)(2)(3)(4)
Il faut compter les permutations avec les points fixes. Mais j'ai perdu plusieurs heures sans trouver la solution avant d'aller en ligne. Apparament, on peux utiliser la formule d’inclusion-exclusion du troisième exercice pour cette tâche. Je recommence à partir de ça.
$$\begin{aligned} \Omega &= \text{ permutations de }n\text{ objets} \\ |\Omega| &= n! \\ \sigma(i) &= \text{ la lettre qui est déposée dans boîte }i \\ A_i &= \text{ les permutations ou }\sigma(i) = i \\ \mathbb{P}(\cup_{m=1}^n A_m) &= \sum_{k=1}^n (-1)^{k+1} p_k \\ p_k &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \mathbb{P}(A_{i_1} \cap \cdots \cap A_{i_k}) \\ &= \sum_{1 \leq i_1 \lt \cdots \lt i_k \leq n} \frac{(n-k)!}{|\Omega|} \\ &= {n \choose k} \frac{(n-k)!}{n!} \\ &= \frac{n!}{(n-k)!k!} \cdot \frac{(n-k)!}{n!} \\ &= \frac{1}{k!} \\ \mathbb{P}(\cup_{m=1}^n A_m) &= \sum_{k=1}^n (-1)^{k+1} \frac{1}{k!} \\ \mathbb{P}(\cup_{m=1}^4 A_m) &= \frac{1}{1!} - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} \\ \end{aligned}$$On veut voir 4, 15, 76, 455, comme on a trouver avec le code source ci-dessus.
In [13]:
(frac(1,1) - frac(1,2) + frac(1,6) - frac(1,24)) * 24
Out[13]:
In [14]:
from sympy import binomial as bn, factorial as fact
def probabilite_au_moins_une_correcte(n):
somme = 0
for k in range(1,n+1):
somme += (-1)**(k+1) * frac(1, fact(k))
return somme
[fact(i) * probabilite_au_moins_une_correcte(i) for i in range(1,7)]
Out[14]:
Le voilà !
La probabilité d'une distribution correcte est $\frac{1}{n!}$. La probabilité qu'au moins une lettre parvienne au bon destinataire est donnée par $\mathbb{P}(\cup_{m=1}^n A_m)$ ci-dessus. La probabilité qu'aucune lettre n'arrive au bon destinataire est $1-\mathbb{P}(\cup_{m=1}^n A_m)$. Et $d_n$ est égal à $n!(1-\mathbb{P}(\cup_{m=1}^n A_m))$.
In [14]: